package day0215;

import java.util.Arrays;

public class QuickSort {





    public static void main(String[] args) {
        int[] arr = {6, 1, 2, 7, 9, 3, 4, 5, 6, 10, 8};

        quickSort(arr);

        System.out.println(Arrays.toString(arr));
    }

    static void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    static void quickSort(int[] arr, int left, int right) {
        // 递归结束条件
        if (left >= right) {
            return;
        }

        int l = left;
        int r = right;
        int num = arr[left];

        while (left < right){
            while (arr[right] >= num && left < right) {
                right --;
            }

            while (arr[left] <= num && left < right) {
                left ++;
            }

            if (left < right) {
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
            }
        }

        arr[l] = arr[left];
        arr[left] = num;

        // 对左边进行快排
        quickSort(arr, l, left - 1);
        // 对右边进行快排
        quickSort(arr, left + 1 , r);
    }
}
